package com.springboot.study.tests.trees;

import java.util.*;

/**
 * @Author: guodong
 * @Date: 2021/12/24 17:05
 * @Version: 1.0
 * @Description:
 */
public class binaryTree {

    public static void main(String[] args) {
        List<Integer> list=new ArrayList<Integer>();
        //构造二叉树
        TreeNode treeNode6=new TreeNode(2,null,null);
        TreeNode treeNode5=new TreeNode(1,null,null);
        TreeNode treeNode4=new TreeNode(7,null,null);
        TreeNode treeNode3=new TreeNode(6,treeNode5,treeNode6);
        TreeNode treeNode2=new TreeNode(5,treeNode4,null);
        TreeNode root=new TreeNode(3,treeNode2,treeNode3);
        list=DFS(root);
        System.out.println("深度优先遍历:"+list);
        list=BFS(root);
        System.out.println("广度优先遍历:"+list);
    }

    /**
     * 深度优先遍历
     * @param root
     * @return
     */
    public static List<Integer> DFS(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        if(root==null){
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode t = stack.pop();
            if(t.right != null){
                stack.push(t.right);
            }
            if(t.left != null){
                stack.push(t.left);
            }
            list.add(t.val);
        }
        return list;
    }

    /**
     * 广度优先遍历
     * @param root
     * @return
     */
    public static List<Integer> BFS(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<Integer> list=new ArrayList<Integer>();
        if(root==null){
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode t = queue.remove();
            if(t.left!=null){
                queue.add(t.left);
            }
            if(t.right!=null){
                queue.add(t.right);
            }
            list.add(t.val);
        }
        return list;
    }


}
